Termination proof of /tmp/tmpob468O/incList.itrs

Termination of the given ITRSProblem could successfully be proven:

↳ ITRS

  ↳ ITRStoIDPProof

ITRS problem:
The following domains are used:

z

The TRS R consists of the following rules:

g(x, cons(y, ys)) → cons(+@z(x, y), g(x, ys))

The set Q consists of the following terms:

g(x0, cons(x1, x2))

Added dependency pairs

↳ ITRS

  ↳ ITRStoIDPProof

    ↳ IDP

      ↳ UsableRulesProof

I DP problem:
The following domains are used:

z

The ITRS R consists of the following rules:

g(x, cons(y, ys)) → cons(+@z(x, y), g(x, ys))

The integer pair graph contains the following rules and edges:

(0): G(x[0], cons(y[0], ys[0])) → G(x[0], ys[0])

(0) -> (0), if ((ys[0] →^* cons(y[0]a, ys[0]a))∧(x[0] →^* x[0]a))

The set Q consists of the following terms:

g(x0, cons(x1, x2))

As all Q-normal forms are R-normal forms we are in the innermost case. Hence, by the usable rules processor [LPAR04] we can delete all non-usable rules [FROCOS05] from R.

↳ ITRS

  ↳ ITRStoIDPProof

    ↳ IDP

      ↳ UsableRulesProof

        ↳ IDP

          ↳ IDPNonInfProof

I DP problem:
The following domains are used:none

R is empty.
The integer pair graph contains the following rules and edges:

(0): G(x[0], cons(y[0], ys[0])) → G(x[0], ys[0])

(0) -> (0), if ((ys[0] →^* cons(y[0]a, ys[0]a))∧(x[0] →^* x[0]a))

The set Q consists of the following terms:

g(x0, cons(x1, x2))

The constraints were generated the following way:
The DP Problem is simplified using the Induction Calculus [NONINF] with the following steps:
Note that final constraints are written in bold face.

For Pair G(x, cons(y, ys)) → G(x, ys) the following chains were created:

We consider the chain G(x[0], cons(y[0], ys[0])) → G(x[0], ys[0]), G(x[0], cons(y[0], ys[0])) → G(x[0], ys[0]), G(x[0], cons(y[0], ys[0])) → G(x[0], ys[0]) which results in the following constraint:
(1)    (ys[0]=cons(y[0]1, ys[0]1)∧x[0]=x[0]1∧ys[0]1=cons(y[0]2, ys[0]2)∧x[0]1=x[0]2 ⇒ G(x[0]1, cons(y[0]1, ys[0]1))≥G(x[0]1, ys[0]1)∧(U^Increasing(G(x[0]1, ys[0]1)), ≥))

We simplified constraint (1) using rules (III), (IV) which results in the following new constraint:
(2)    (G(x[0], cons(y[0]1, cons(y[0]2, ys[0]2)))≥G(x[0], cons(y[0]2, ys[0]2))∧(U^Increasing(G(x[0]1, ys[0]1)), ≥))

We simplified constraint (2) using rule (POLY_CONSTRAINTS) which results in the following new constraint:
(3)    ((U^Increasing(G(x[0]1, ys[0]1)), ≥)∧1 ≥ 0)

We simplified constraint (3) using rule (IDP_POLY_SIMPLIFY) which results in the following new constraint:
(4)    ((U^Increasing(G(x[0]1, ys[0]1)), ≥)∧1 ≥ 0)

We simplified constraint (4) using rule (POLY_REMOVE_MIN_MAX) which results in the following new constraint:
(5)    (1 ≥ 0∧(U^Increasing(G(x[0]1, ys[0]1)), ≥))

We simplified constraint (5) using rule (IDP_UNRESTRICTED_VARS) which results in the following new constraint:
(6)    (0 = 0∧0 = 0∧0 = 0∧0 = 0∧(U^Increasing(G(x[0]1, ys[0]1)), ≥)∧1 ≥ 0)

To summarize, we get the following constraints P_≥ for the following pairs.

G(x, cons(y, ys)) → G(x, ys)
- (0 = 0∧0 = 0∧0 = 0∧0 = 0∧(U^Increasing(G(x[0]1, ys[0]1)), ≥)∧1 ≥ 0)

The constraints for P_> respective P_bound are constructed from P_≥ where we just replace every occurence of "t ≥ s" in P_≥ by "t > s" respective "t ≥ c". Here c stands for the fresh constant used for P_bound.
Using the following integer polynomial ordering the resulting constraints can be solved
Polynomial interpretation over integers with natural coefficients for non-tuple symbols [NONINF][POLO]:

POL(cons(x₁, x₂)) = 1 + x₂
POL(TRUE) = 0
POL(G(x₁, x₂)) = -1 + (2)x₂ + (-1)x₁
POL(FALSE) = 0
POL(undefined) = 0

The following pairs are in P_>:

G(x[0], cons(y[0], ys[0])) → G(x[0], ys[0])

The following pairs are in P_bound:

G(x[0], cons(y[0], ys[0])) → G(x[0], ys[0])

The following pairs are in P_≥:
none

There are no usable rules.

↳ ITRS

  ↳ ITRStoIDPProof

    ↳ IDP

      ↳ UsableRulesProof

        ↳ IDP

          ↳ IDPNonInfProof

            ↳ IDP

              ↳ IDependencyGraphProof

I DP problem:
The following domains are used:none

R is empty.
The integer pair graph is empty.
The set Q consists of the following terms:

g(x0, cons(x1, x2))

The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 0 SCCs.